ABC253 C - Max - Min Query - 競プロ

ABC253 C - Max - Min Query

https://atcoder.jp/contests/abc253/tasks/abc253_c

提出

code: python

from collections import defaultdict

q = int(input())

queries = list(map(int, input().split())) for _ in range(q)

d = defaultdict(int)

minmax = set()

for query in queries:

if (query0 == 1):

d[query1] += 1

minmax.add(query1)

elif (query0 == 2):

res = min(d[query1], query2)

if (res == d[query1]):

minmax.discard(query1)

d[query1] -= res

else:

print(max(minmax) - min(minmax))

解答

code: python

from collections import defaultdict

import heapq

q = int(input())

queries = list(map(int, input().split())) for _ in range(q)

d = defaultdict(int)

maxq = []

minq = []

for query in queries:

n = query0

if n == 1:

_, x = query

dx += 1

heapq.heappush(minq, x)

# heapqは最小値しか取り出せないから-を掛ける

heapq.heappush(maxq, -x)

elif n == 2:

_, x, c = query

dx -= min(c , dx)

else:

qmin = heapq.heappop(minq)

while dqmin == 0:

# 次の最小値を取り出す

qmin = heapq.heappop(minq)

qmax = heapq.heappop(maxq)

qmax *= -1

while dqmax == 0:

# 次の最大値を取り出す

qmax = heapq.heappop(maxq)

qmax *= -1

print(qmax - qmin)

# 最小値、最大値をheapq へ戻す

heapq.heappush(minq, qmin)

heapq.heappush(maxq, -qmax)

テーマ

メモ

https://atcoder.jp/contests/abc253/submissions/32136208

提出

TLE

code: python

from collections import defaultdict

q = int(input())

queries = list(map(int, input().split())) for _ in range(q)

d = defaultdict(int)

# max と min の管理

# 0 になったとき

for query in queries:

n = query0

if n == 1:

_, x = query

dx += 1

# if x > maxn:

# maxn = x

# if x < minn:

# minn = x

elif n == 2:

_, x, c = query

dx -= c

if dx < 0:

dx = 0

else:

maxn = -1

minn = 1e9

for k, v in d.items():

if v == 0:

continue

if k > maxn:

maxn = k

if k < minn:

minn = k

print(maxn - minn)